package algorithms.sorting

/**
 * [Running Time of Algorithms](https://www.hackerrank.com/challenges/runningtime)
 */
// Complete the runningTime function below.
fun runningTime(arr: Array<Int>): Int {
    val n = arr.size
    var shifts = 0
    fun insertion(m: Int, arr1: Array<Int>) {
        val temp = arr1[m - 1]
        for (i in m - 2 downTo 0) {
            if (arr1[i] > temp) {
                arr1[i + 1] = arr1[i]
                shifts++
            } else {
                arr1[i + 1] = temp
                return
            }
        }
        arr1[0] = temp
    }

    for (i in 2..n) {
        insertion(i, arr)
    }

    return shifts
}